/*!
 Temelia - Graph samples.

 Copyright (C) 2008 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "include/samples.h"
#include <temelia/graph.h>
#include <temelia/graph_constants.h>
#include <temelia/graph_matrix.h>
#include <temelia/graph_sparse_matrix.h>
#include <temelia/graph_list.h>
#include <temelia/pair.h>

static void edge_handler(edge_t edge_t, void *fout)
{
	vertex_t v1, v2;
	if (!edge_t)
		return;

	v1 = edge_get_vertex1(edge_t);
	v2 = edge_get_vertex2(edge_t);

	PRINT("[edge_t] ");
	PRINT("Identifier1 %lu, Identifier2 %lu, Cost %lf, Key %p, Label |%s|, Type %d\n",
			vertex_get_identifier(v1), vertex_get_identifier(v2),
			edge_get_cost(edge_t), edge_get_key(edge_t),
			edge_get_label(edge_t), edge_get_type(edge_t));
}

static void vertex_handler(vertex_t v, void *fout)
{
	PRINT("[vertex_t] ");
	PRINT("Identifier %lu, "
			"Color %d, "
			"Cost %lf, "
			"Data %p, "
			"Label |%s|, "
			"Time start %lu, "
			"Time stop %lu, "
			"Parent identifier %lu, "
			"Visited %d\n", vertex_get_identifier(v), vertex_get_color(v),
			vertex_get_cost(v), vertex_get_key(v), vertex_get_label(v),
			vertex_get_time_start(v), vertex_get_time_stop(v),
			vertex_get_parent_identifier(v), vertex_get_visited(v));
}

static void list_handler(void *x, void *fout)
{
	PRINT("%lu ", (unsigned long) x);
}

static void linked_list_handler(void *x, void *fout)
{
	PRINT("New list component :\n");
	linked_list_iterate(x, list_handler, fout, 1);
	PRINT("\n\n");
	linked_list_delete(x);
}

void pair_handler(void *x, void *fout)
{
	pair_t p = x;

	if (p == NULL)
		return;

	PRINT("[%lu, %lu]\n", (unsigned long) pair_get_key(p),
			(unsigned long) pair_get_value(p));
	pair_delete(p);
}

void kruskal_handler(void *x, void *context)
{
	if ((*(unsigned long *) context) != (unsigned long) -1)
		PRINT("[%lu, %lu]\n", *((unsigned long *) context),
				(unsigned long) x);
	*(unsigned long *) context = (unsigned long) x;
}

static void my_vertex_delete(vertex_t vertex)
{
	free(vertex_get_label(vertex));
	vertex_delete(vertex);
}

static void my_edge_delete(edge_t edge)
{
	free(edge_get_label(edge));
	edge_delete(edge);
}

int columns, m_column;

void double_matrix_handler(void *key, void *context)
{
	double_handler(key, context);
	m_column++;

	if (m_column == columns)
	{
		m_column = 0;
		PRINT("\n");
	}
}

void unsigned_matrix_handler(void *key, void *context)
{
	unsigned_int_handler(key, context);

	m_column++;

	if (m_column == columns)
	{
		m_column = 0;
		PRINT("\n");
	}
}

// Sample for vertex_t handling : add, remove, check, print and set/get functions.
static void sample1(graph_implementation_t impl)
{
	graph_t graph;
	vertex_t vertex;
	int n = 5, i;
	int *vertices;

	PRINT("\n\n Sample 1 started \n\n");

	graph = graph_new(n, impl, NULL, NULL);
	vertices = (int *) malloc(n * sizeof(int));

	for (i = 0; i < n; i++)
	{
		// Add n unnamed vertices.
		vertices[i] = graph_add_vertex(graph, NULL, NULL);
		PRINT("Allocated vertex_t : %d\n", vertices[i]);
		if (rand() % 2)
		{
			PRINT("Removing vertex_t #%d\n", vertices[i]);
			vertex_delete(graph_remove_vertex(graph, vertices[i]));
		}
	}

	for (i = 0; i < n; i++)
	{
		if (graph_is_vertex(graph, vertices[i]))
			PRINT("#%d is a valid vertex_t\n", vertices[i]);
		else
			PRINT("#%d is not a valid vertex_t\n", vertices[i]);
	}

	// Set some vertex_t parameters.
	vertex_set_label(graph_get_vertex(graph, 0), "vertex1");
	vertex_set_key(graph_get_vertex(graph, 0), (void *) 0x1234);

	PRINT("vertex_t label : %s\n", vertex_get_label(graph_get_vertex(graph, 0)));
	PRINT("vertex_t data : %p\n", vertex_get_key(graph_get_vertex(graph, 0)));

	vertex = graph_get_vertex(graph, 0);

	PRINT("%p %d %.0lf %p %lu %s\n", vertex, vertex_get_color(vertex), vertex_get_cost(vertex),
			vertex_get_key(vertex), vertex_get_identifier(vertex), vertex_get_label(vertex));

	vertex_set_time_start(vertex, 10);
	vertex_set_time_stop(vertex, 10);
	vertex_set_visited(vertex, 1);
	vertex_set_parent_identifier(vertex, 5);
	PRINT("Start : %lu | Stop : %lu | Visited %d | Parent %lu \n",
			vertex_get_time_stop(vertex), vertex_get_time_start(vertex),
			vertex_get_visited(vertex), vertex_get_parent_identifier(vertex));

	PRINT("Invalid pointer : %p\n", graph_get_vertex(graph, 200));

	free(vertices);
	graph_delete(graph);

	PRINT("\n\n Sample 1 ended \n\n");
}

// Sample for edge_t handling : add, remove and set/get functions.
static void sample2(graph_implementation_t impl)
{
	graph_t graph = NULL;
	int i, n = 5, m = 10;
	char buffer[50];
	char edge_t[10][2] =
	{
	{ 0, 1 },
	{ 0, 2 },
	{ 0, 3 },
	{ 0, 4 },
	{ 1, 2 },
	{ 1, 0 },
	{ 2, 0 },
	{ 3, 0 },
	{ 4, 0 },
	{ 2, 1 } };

	PRINT("\n\n Sample 2 started \n\n");

	graph = graph_new(n, impl, my_vertex_delete, my_edge_delete);
	PRINT("Graph empty %d\n", graph_is_empty(graph));

	// Add some vertex_t
	for (i = 0; i < n; i++)
	{
		sprintf(buffer, "vertex_t %d", i);
		graph_add_vertex(graph, my_strdup(buffer), NULL);
	}

	for (i = 0; i < n; i++)
		PRINT("%s\n", vertex_get_label(graph_get_vertex(graph, i)));

	// Add some edges
	for (i = 0; i < m; i++)
	{
		sprintf(buffer, "edge_t [%d, %d]", edge_t[i][0], edge_t[i][1]);
		graph_add_edge(graph, edge_t[i][0], edge_t[i][1], rand() % 1000,
				my_strdup(buffer), NULL);
	}

	PRINT("\nVertices \n\n");
	graph_iterate_vertices(graph, vertex_handler, NULL);

	// Print edges and vertices from current graph_t.
	PRINT("\nEdges \n\n");
	graph_iterate_edges(graph, edge_handler, NULL);

	my_vertex_delete(graph_remove_vertex(graph, 0));

	// This is how you should delete an edge_t.
	// Obtain the pointer, do whatever you want with it
	// and then call free.
	my_edge_delete(graph_remove_edge(graph, 1, 2));

	PRINT("\n\nNew edges \n\n");
	graph_iterate_edges(graph, edge_handler, NULL);
	PRINT("\nVertices \n\n");
	graph_iterate_vertices(graph, vertex_handler, NULL);

	PRINT("Is_edge(0, 1) = %d, Is_edge(2, 1) = %d, Is_edge(-1, 128) =  %d\n", graph_is_edge(graph, 0, 1),
			graph_is_edge(graph, 2, 1), graph_is_edge(graph, -1, 128));
	PRINT("Edges number : %lu\n", graph_get_dimension(graph));
	PRINT("Vertices number : %lu\n", graph_get_size(graph));
	PRINT("Graph empty %d\n", graph_is_empty(graph));

	edge_set_cost(graph_get_edge(graph, 2, 1), 0.12);

	// Change label, by freeing the old pointer
	// and setting a new value to the stored label
	free(edge_get_label(graph_get_edge(graph, 2, 1)));
	edge_set_label(graph_get_edge(graph, 2, 1), my_strdup("new_label"));

	edge_set_key(graph_get_edge(graph, 2, 1), (void *) 0x123);
	PRINT("Cost %lf, Label %s, Key %p\n", edge_get_cost(graph_get_edge(graph, 2, 1)),
			edge_get_label(graph_get_edge(graph, 2, 1)),
			edge_get_key(graph_get_edge(graph, 2, 1)));

	for (i = 0; i < n; i++)
	{
		PRINT("Degree(%d) = %lu, ", i, graph_vertex_degree(graph, i));
		PRINT("In degree(%d) = %lu, ", i, graph_vertex_in_degree(graph, i));
		PRINT("Out degree(%d) = %lu\n", i, graph_vertex_out_degree(graph, i));
	}

	graph_delete(graph);

	PRINT("\n\n Sample 2 ended \n\n");
}

// Sample for DFS and BFS
static void sample3(graph_implementation_t impl)
{
	graph_t graph;
	unsigned long n = 5, i, m = 10;
	char buffer[50][50];
	char edges[10][2] =
	{
	{ 0, 1 },
	{ 0, 2 },
	{ 0, 3 },
	{ 0, 4 },
	{ 1, 2 },
	{ 1, 0 },
	{ 2, 0 },
	{ 3, 0 },
	{ 4, 0 },
	{ 2, 1 } };

	PRINT("\n\n Sample 3 started \n\n");

	graph = graph_new(n + 1, impl, NULL, NULL);

	for (i = 0; i < n; i++)
	{
		sprintf(buffer[i], "vertex_t %lu", i);
		graph_add_vertex(graph, buffer[i], NULL);
	}

	for (i = 0; i < m; i++)
		graph_add_edge(graph, edges[i][0], edges[i][1], 1, NULL, NULL);

	PRINT("=== DFS travel ===\n");

	// See the vertices vectors after the travel.
	PRINT("DFS starting from 4\n");
	graph_dfs(graph, 4);
	graph_iterate_vertices(graph, vertex_handler, NULL);

	// Reset vertices.
	graph_reset_vertices(graph);

	// Add an isolated vertex_t and start complete DFS travel.
	graph_add_vertex(graph, "Isolated", NULL);
	PRINT("Complete DFS travel\n");
	graph_dfs(graph, -1);
	graph_iterate_vertices(graph, vertex_handler, NULL);

	// Reset vertices.
	PRINT("\n=== Printing the graph edges ===\n");
	graph_reset_vertices(graph);
	graph_add_edge(graph, 4, 5, 123, "edge_aux", NULL);
	graph_iterate_edges(graph, edge_handler, NULL);

	PRINT("\n=== BFS travel ===\n");
	PRINT("BFS starting from 2\n");
	graph_bfs(graph, 2);
	graph_iterate_vertices(graph, vertex_handler, NULL);

	// Reset vertices.
	graph_reset_vertices(graph);

	PRINT("Complete BFS travel\n");
	graph_bfs(graph, -1);
	graph_iterate_vertices(graph, vertex_handler, NULL);

	graph_reset_vertices(graph);
	graph_dfs_edges_classification(graph);
	PRINT("DFS edges classification\n");
	graph_iterate_edges(graph, edge_handler, NULL);

	graph_reset_vertices(graph);
	graph_bfs_edges_classification(graph);
	PRINT("BFS edges classification\n");
	graph_iterate_edges(graph, edge_handler, NULL);

	graph_delete(graph);

	PRINT("\n\n Sample 3 ended \n\n");
}

static void sample4(graph_implementation_t impl)
{
	graph_t graph;
	unsigned long n = 9, i, m = 11, v1, v2;
	char buffer[50][50];
	linked_list_t first_set, second_set, cycles, cut_vertex, bridges,
			biconex_components;

	char edges[11][2] =
	{
	{ 0, 1 },
	{ 0, 2 },
	{ 1, 2 },
	{ 2, 3 },
	{ 2, 5 },
	{ 3, 4 },
	{ 4, 5 },
	{ 5, 6 },
	{ 6, 7 },
	{ 6, 8 },
	{ 7, 8 } };

	PRINT("\n\n Sample 4 started \n\n");

	graph = graph_new(n, impl, NULL, NULL);

	for (i = 0; i < n; i++)
	{
		sprintf(buffer[i], "vertex_t %lu", i);
		graph_add_vertex(graph, buffer[i], NULL);
	}

	for (i = 0; i < m; i++)
	{
		graph_add_edge(graph, edges[i][0], edges[i][1], 1, NULL, NULL);
		graph_add_edge(graph, edges[i][1], edges[i][0], 1, NULL, NULL);
	}

	first_set = linked_list_new();
	second_set = linked_list_new();

	PRINT("Graph bipartite : %d\n", graph_bipartite(graph, first_set, second_set));
	PRINT(" First half\n");
	linked_list_iterate(first_set,
			(void(*)(void *, void *)) unsigned_int_handler, NULL, 1);
	PRINT("\n Second half");
	linked_list_iterate(second_set,
			(void(*)(void *, void *)) unsigned_int_handler, NULL, 1);

	PRINT("\n\nGraph diameter : %lu\n", graph_diameter(graph, &v1, &v2));
	PRINT("Vertices that form the diameter are %lu %lu\n\n", v1, v2);

	cycles = linked_list_new();
	graph_cycles(graph, cycles);

	PRINT("== The graph cycles ==\n");
	linked_list_iterate(cycles, linked_list_handler, NULL, 1);
	PRINT("\n\n");

	cut_vertex = linked_list_new();
	graph_articulation_points(graph, cut_vertex);

	PRINT("== Cut-vertices ==\n");
	linked_list_iterate(cut_vertex,
			(void(*)(void *, void *)) unsigned_int_handler, NULL, 1);

	bridges = linked_list_new();
	graph_bridges(graph, bridges);
	PRINT("\n== Bridges ==\n");
	linked_list_iterate(bridges, pair_handler, NULL, 1);

	biconex_components = linked_list_new();
	graph_biconex_components(graph, biconex_components);
	PRINT("\nThe biconex components are :\n");
	linked_list_iterate(biconex_components, linked_list_handler, NULL, 1);

	linked_list_delete(biconex_components);
	linked_list_delete(bridges);
	linked_list_delete(cut_vertex);
	linked_list_delete(cycles);
	linked_list_delete(first_set);
	linked_list_delete(second_set);
	graph_delete(graph);

	PRINT("\n\n Sample 4 ended \n\n");
}

static void connected_components_sample(graph_implementation_t impl)
{
	graph_t graph;
	unsigned long n = 5, i, m = 4;
	char buffer[50][50];
	linked_list_t connected_components;

	char edges[10][2] =
	{
	{ 0, 1 },
	{ 1, 0 },
	{ 3, 2 },
	{ 2, 3 } };

	graph = graph_new(n + 1, impl, NULL, NULL);

	for (i = 0; i < n; i++)
	{
		sprintf(buffer[i], "vertex_t %lu", i);
		graph_add_vertex(graph, buffer[i], NULL);
	}

	for (i = 0; i < m; i++)
		graph_add_edge(graph, edges[i][0], edges[i][1], 1, NULL, NULL);

	connected_components = linked_list_new();
	graph_connected_components(graph, connected_components, 0);
	linked_list_iterate(connected_components, linked_list_handler, NULL, 1);
	linked_list_delete(connected_components);
	graph_delete(graph);
}

static void strongly_connected_components_sample(graph_implementation_t impl)
{
	graph_t graph;
	unsigned long n = 8, i, m = 14;
	char buffer[50][50];
	linked_list_t strongly_connected_components;

	char edges[14][2] =
	{
	{ 0, 1 },
	{ 1, 2 },
	{ 1, 4 },
	{ 1, 5 },
	{ 2, 3 },
	{ 2, 6 },
	{ 3, 2 },
	{ 3, 7 },
	{ 7, 6 },
	{ 7, 3 },
	{ 6, 5 },
	{ 5, 6 },
	{ 4, 5 },
	{ 4, 0 } };

	graph = graph_new(n, impl, NULL, NULL);

	for (i = 0; i < n; i++)
	{
		sprintf(buffer[i], "vertex_t %lu", i);
		graph_add_vertex(graph, buffer[i], NULL);
	}

	for (i = 0; i < m; i++)
		graph_add_edge(graph, edges[i][0], edges[i][1], 1, NULL, NULL);

	strongly_connected_components = linked_list_new();
	graph_strongly_connected_components(graph, strongly_connected_components);
	linked_list_iterate(strongly_connected_components, linked_list_handler,
			NULL, 1);
	linked_list_delete(strongly_connected_components);
	graph_delete(graph);
}

void topological_sort_sample(graph_implementation_t impl)
{
	graph_t graph;
	unsigned long n = 5, i, m = 7;
	char buffer[50][50];
	linked_list_t topological_sort;

	char edges[10][2] =
	{
	{ 0, 1 },
	{ 0, 2 },
	{ 1, 2 },
	{ 2, 3 },
	{ 1, 3 },
	{ 4, 0 },
	{ 1, 4 } };

	graph = graph_new(n + 1, impl, NULL, NULL);

	for (i = 0; i < n; i++)
	{
		sprintf(buffer[i], "vertex_t %lu", i);
		graph_add_vertex(graph, buffer[i], NULL);
	}

	for (i = 0; i < m; i++)
		graph_add_edge(graph, edges[i][0], edges[i][1], 1, NULL, NULL);

	topological_sort = linked_list_new();

	PRINT("Invalid topological sort : %d\n",
			graph_topological_sort(graph, topological_sort));
	linked_list_iterate(topological_sort, list_handler, NULL, 1);
	PRINT("\n");

	// Remove edge that forms the cycle 0 -> 1 -> 4 -> 0
	edge_delete(graph_remove_edge(graph, 1, 4));
	PRINT("Valid topological sort : %d\n",
			graph_topological_sort(graph, topological_sort));
	linked_list_iterate(topological_sort, list_handler, NULL, 1);
	PRINT("\n");

	linked_list_delete(topological_sort);
	graph_delete(graph);
}

static void sample5(graph_implementation_t impl)
{
	PRINT("\n\n Sample 5 started \n\n");

	PRINT("== Connected components ==\n");
	connected_components_sample(impl);
	PRINT("\n== Strongly connected components ==\n");
	strongly_connected_components_sample(impl);
	PRINT("\n== Topological sort ==\n");
	topological_sort_sample(impl);

	PRINT("\n\n Sample 5 ended \n\n");
}

static void sample6(graph_implementation_t impl)
{
	graph_t graph;
	unsigned long n = 5, m = 9, i, j;
	char buffer[50][50];
	matrix_t fw_distances, fw_parents, j_distances, j_parents;
	vector_t bf_distances, bf_parents, d_distances, d_parents;

	char edges[10][3] =
	{
	{ 0, 1, 6 },
	{ 0, 4, 2 },
	{ 1, 3, 8 },
	{ 1, 2, 5 },
	{ 1, 4, -4 },
	{ 2, 1, -2 },
	{ 3, 2, 3 },
	{ 3, 4, 9 },
	{ 4, 2, 7 } };
	graph = graph_new(n + 1, impl, NULL, NULL);

	for (i = 0; i < n; i++)
	{
		sprintf(buffer[i], "vertex_t %lu", i);
		graph_add_vertex(graph, buffer[i], NULL);
	}

	for (i = 0; i < m; i++)
		graph_add_edge(graph, edges[i][0], edges[i][1], edges[i][2], NULL, NULL);

	fw_distances = matrix_new(n, n);
	fw_parents = matrix_new(n, n);
	j_distances = matrix_new(n, n);
	j_parents = matrix_new(n, n);

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			matrix_set_key_at(fw_distances, i, j, malloc(sizeof(double)));
			matrix_set_key_at(fw_parents, i, j, (void *) -1);

			matrix_set_key_at(j_distances, i, j, malloc(sizeof(double)));
			matrix_set_key_at(j_parents, i, j, (void *) -1);
		}
	}

	graph_floyd_warshall(graph, fw_distances, fw_parents);

	m_column = 0;
	columns = n;
	PRINT("\nDistances matrix : \n");
	matrix_iterate(fw_distances, double_matrix_handler, NULL);

	PRINT("\nParents matrix : \n");
	matrix_iterate(fw_parents, unsigned_matrix_handler, NULL);

	bf_parents = vector_new(n);
	bf_distances = vector_new(n);

	for (i = 0; i < n; i++)
	{
		vector_push_back(bf_distances, malloc(sizeof(double)));
		vector_push_back(bf_parents, (void *) -1);
	}

	PRINT("\n\n");

	for (i = 0; i < n; i++)
	{
		PRINT("Bellman Ford (%lu) result %d\n", i, graph_bellman_ford(graph, i,
						bf_distances, bf_parents));
		PRINT("Distances : \n");
		vector_iterate(bf_distances, (void(*)(void *, void *)) double_handler,
				NULL);
		PRINT("\nParent : \n");
		vector_iterate(bf_parents,
				(void(*)(void *, void *)) unsigned_int_handler, NULL);
		PRINT("\n\n");
	}

	d_parents = vector_new(n);
	d_distances = vector_new(n);

	for (i = 0; i < n; i++)
	{
		vector_push_back(d_distances, malloc(sizeof(double)));
		vector_push_back(d_parents, (void *) -1);
	}

	PRINT("\n\n");

	for (i = 0; i < n; i++)
	{
		PRINT("Dijkstra (%lu) result\n", i);
		graph_dijkstra(graph, i, d_distances, d_parents);
		PRINT("Distances : \n");
		vector_iterate(d_distances, (void(*)(void *, void *)) double_handler,
				NULL);
		PRINT("\nParent : \n");
		vector_iterate(d_parents,
				(void(*)(void *, void *)) unsigned_int_handler, NULL);
		PRINT("\n\n");
	}

	graph_johnson(graph, j_distances, j_parents);

	PRINT("\nJohnson : \nDistances matrix : \n");
	matrix_iterate(j_distances, double_matrix_handler, NULL);

	PRINT("\nParents matrix : \n");
	matrix_iterate(j_parents, unsigned_matrix_handler, NULL);

	for (i = 0; i < n; i++)
	{
		free(vector_get_key_at(bf_distances, i));
		free(vector_get_key_at(d_distances, i));

		for (j = 0; j < n; j++)
		{
			free(matrix_get_key_at(fw_distances, i, j));
			free(matrix_get_key_at(j_distances, i, j));
		}
	}

	vector_delete(bf_distances);
	vector_delete(d_distances);

	vector_delete(bf_parents);
	vector_delete(d_parents);

	matrix_delete(fw_distances);
	matrix_delete(fw_parents);
	matrix_delete(j_distances);
	matrix_delete(j_parents);

	graph_delete(graph);
}

static void sample7(graph_implementation_t impl)
{
	graph_t graph;

	linked_list_t prim_mst, kruskal_mst;
	unsigned long i, n = 9, m = 28;
	char edges[28][3] =
	{
	{ 0, 1, 4 },
	{ 1, 0, 4 },
	{ 0, 7, 8 },
	{ 7, 0, 8 },
	{ 1, 7, 11 },
	{ 7, 1, 11 },
	{ 7, 8, 7 },
	{ 8, 7, 7 },
	{ 1, 2, 8 },
	{ 2, 1, 8 },
	{ 2, 8, 2 },
	{ 8, 2, 2 },
	{ 6, 8, 6 },
	{ 8, 6, 6 },
	{ 6, 7, 1 },
	{ 7, 6, 1 },
	{ 2, 3, 7 },
	{ 3, 2, 7 },
	{ 2, 5, 4 },
	{ 5, 2, 4 },
	{ 3, 5, 14 },
	{ 5, 3, 14 },
	{ 3, 4, 9 },
	{ 4, 3, 9 },
	{ 4, 5, 10 },
	{ 5, 4, 10 },
	{ 5, 6, 2 },
	{ 6, 5, 2 } };
	unsigned long kruskal_context = (unsigned long) -1;

	graph = graph_new(n, impl, NULL, NULL);

	prim_mst = linked_list_new();

	for (i = 0; i < n; i++)
		graph_add_vertex(graph, NULL, NULL);

	for (i = 0; i < m; i++)
		graph_add_edge(graph, edges[i][0], edges[i][1], edges[i][2], NULL, NULL);

	PRINT("Prim cost : %lf\n", graph_prim(graph, 0, prim_mst));
	linked_list_iterate(prim_mst, pair_handler, NULL, 1);
	linked_list_delete(prim_mst);

	PRINT("Kruskal cost : %lf\n", graph_kruskal(graph, 0, &kruskal_mst));
	linked_list_iterate(kruskal_mst, kruskal_handler, &kruskal_context, 1);
	linked_list_delete(kruskal_mst);

	graph_delete(graph);
}

static void sample8(graph_implementation_t impl)
{
	graph_t graph;
	matrix_t ford_fulkerson, edmonds_karp;
	unsigned long n = 4, i, j, m = 5;
	char buffer[50][50];

	char edges[10][2] =
	{
	{ 0, 1 },
	{ 0, 2 },
	{ 1, 2 },
	{ 2, 3 },
	{ 1, 3 } };
	double cost[10] =
	{ 1000, 1000, 1, 1000, 1000 };

	PRINT("\n\n Sample 8 started \n\n");

	graph = graph_new(n, impl, NULL, NULL);

	for (i = 0; i < n; i++)
	{
		sprintf(buffer[i], "vertex_t %lu", i);
		graph_add_vertex(graph, buffer[i], NULL);
	}

	for (i = 0; i < m; i++)
	{
		graph_add_edge(graph, edges[i][0], edges[i][1], cost[i], NULL, NULL);
	}

	ford_fulkerson = matrix_new(n, n);
	edmonds_karp = matrix_new(n, n);

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			matrix_set_key_at(ford_fulkerson, i, j, malloc(sizeof(double)));
			matrix_set_key_at(edmonds_karp, i, j, malloc(sizeof(double)));
		}
	}

	PRINT("Max flow by Ford Fulkerson : %lf\n", graph_ford_fulkerson(graph, 0, 3,
					ford_fulkerson));
	PRINT("Max flow by Edmonds Karp : %lf\n", graph_edmonds_karp(graph, 0, 3,
					edmonds_karp));

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			free(matrix_get_key_at(ford_fulkerson, i, j));
			free(matrix_get_key_at(edmonds_karp, i, j));
		}
	}

	matrix_delete(ford_fulkerson);
	matrix_delete(edmonds_karp);
	graph_delete(graph);

	PRINT("\n\n Sample 8 ended \n\n");
}

static void run_graph_algorithms_samples(graph_implementation_t impl)
{
	sample1(impl);
	sample2(impl);
	sample3(impl);
	sample4(impl);
	sample5(impl);
	sample6(impl);
	sample7(impl);
	sample8(impl);
}

void run_graph_samples()
{
	//INIT(stdout);

	run_graph_algorithms_samples(graph_matrix_get_implementation());
	run_graph_algorithms_samples(graph_sparse_matrix_get_implementation());
	run_graph_algorithms_samples(graph_list_get_implementation());

	//DESTROY();
}
